4.13模拟赛T2

什么？？？这题居然是打表？

听到正解的我十分激动，深深体会到了出题人的用心良苦（sang xin bing kuang）

题面： http://www.51nod.com/Challenge/Problem.html#!#problemId=1016

水仙花数 V2

水仙花数是指一个 n 位数 ( n≥3 )，它的每个位上的数字的 n 次幂之和等于它本身。（例如：1^3 + 5^3 + 3^3 = 153，1634 = 1^4 + 6^4 + 3^4 + 4^4）。

给出一个整数M，求 >= M的最小的水仙花数。

输入

复制

一个整数M（10 <= M <= 10^60）

输出

复制

输出>= M的最小的水仙花数，如果没有符合条件的水仙花数，则输出：No Solution

输入样例

复制

300

输出样例

复制

370

你以为这么简单？然鹅，模拟赛里出现了$10^{1000000}$的两个点。

（wnm，这拿头做啊）——————

我们惊奇得发现，，，居然全是没有结果，输出No Solution

你又以为这么简单

too young ,too simple,sometime 咳咳

我们可爱的出题人把No Solution写成了NOSOLUTlON，好像没什么问题？

这，，，个，，，大写 $I$ 其实是 一个小写的 $l$ 。。。。如果不是直接复制，那就**

诶嘿，接下来看一看证明，当然又是我们可爱的出题人小朋友咯（咬牙切齿

证明：$n>60$时，$\sum_{i=0}^{n-1}a_i^n<\sum_{i=0}^{n-1}10^ia_i(0≤a_i≤9)$

引理：$n>60$时，$n9^n<10^{n-1}$

当$n=61$时，通过计算得出$10n(\frac{9}{10})^n<1$

假设当$n=m$时满足此引理成立

那么$(\frac{9}{10})^m=\frac{10m(\frac{9}{10})^m}{10m}<\frac{1}{10m}<\frac{1}{600}$

$10(m+1)(\frac{9}{10})^{m+1}=10m(\frac{9}{10})^{m+1}+10(\frac{9}{10})^{m+1}<\frac{9}{10}+\frac{9}{600}<1$

引理得证

那么左边$≤n9^n$，而右边$≥10^{n-1}$

因为$n9^n<10^{n-1}$，所以左边$<$右边

证毕

然后打表，开心水过~（开心个鬼